package me.zk.practice1.s;

/**
 * @Author: zhang kai
 * @Date: 2023/04/27
 * @Description:
 */
public class S3 {
    public static void main(String[] args) {

        int[] arr = {3,5,2,1,43,33,22,64,74,25,13,27,98,56,100,21,7};
        quickSort(arr);
        for(int x : arr){
            System.out.print(x + " ");
        }

    }

    public static void quickSort(int[] array){
        sort(array,0,array.length-1);


    }

    private static void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int position = partition(array,left,right);

        sort(array,left,position-1);
        sort(array,position+1,right);

    }

    public static int partition(int[] array,int s, int e) {
        int i = s;

        int key = array[s];

        while (s < e) {
            while (s < e &&array[e] >=key){
                e--;
            }
            while (s < e && array[s]<=key) {
                s++;
            }
            //
            swap(array,s,e);
        }
        swap(array,i,s);
        return s;

    }

    public static void swap(int[] array, int n, int m) {
        int temp = array[n];
        array[n] = array[m];
        array[m] = temp;
    }

}
